Disjoint Set
서로소 집합(Disjoin-set)
- 서로소 또는 상호베타 집합들은 서로 중복 포함돤 원소가 없는 집합들이다.
- 교집합이 없는 것
- 집합에 속한 하나의 특정 멤버를 통해 각 집합들을 구분
- 대표자(representative)라고 함
서로소 집합을 표현하는 방법
- 연결리스트
- 트리
서로소 집합 연산(Union-Find)
- Make-Set(x)
- Find-Set(x)
- Union(x,y)
관련 개념
- Union-Find 구현 - Make/Find/Union 연산 구현
- DataStructure - 전체 자료구조 목록